package 中等.动态规划.其他;

/**
 * 给你一个下标从 0 开始、由 n 个整数组成的数组 nums 和一个整数 target 。
 * 你的初始位置在下标 0 。在一步操作中，你可以从下标 i 跳跃到任意满足下述条件的下标 j ：
 * 0 <= i < j < n
 * -target <= nums[j] - nums[i] <= target
 * 返回到达下标 n - 1 处所需的 最大跳跃次数 。
 * 如果无法到达下标 n - 1 ，返回 -1 。
 *
 * @ https://leetcode.cn/problems/maximum-number-of-jumps-to-reach-the-last-index/description/
 * @date 2024/06/28
 */
public class 达到末尾下标所需的最大跳跃次数_2770 {

    public static void main(String[] args) {

    }

    /**
     * 动态规划+选哪个
     * dp[i] 表示到达 i 处所需的 最大跳跃次数
     * 在 [0,i-1] 选择绝对值 <= target 的 nums[j]
     * dp[i] = Math.max(dp[i],dp[j]+1)
     * 注意：还需要判断是否可以到达 n-1 ,加上校验 dp[j] > 0 || j == 0
     */
    public static int maximumJumps(int[] nums, int target) {

        int[] dp = new int[nums.length];

        for (int i = 1; i < dp.length; i++) {

            for (int j = 0; j < i; j++) {
                if (Math.abs(nums[j] - nums[i]) <= target && (dp[j] > 0 || j == 0)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }

        return dp[dp.length - 1] == 0 ? -1 : dp[dp.length - 1];
    }

}
